// 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。
// 你可以选择其中的一个加油站出发，开始时油箱为空。
// 如果你可以绕环路行驶一周，则返回出发时起点加油站的编号，否则返回 -1。

// 说明: 
// 如果题目有解，该答案即为唯一答案。
// 输入数组均为非空数组，且长度相同。
// 输入数组中的元素均为非负数。


const canCompleteCircuit = function (gas: number[], cost: number[]): number {
    let currRemain: number = 0;// 当前累计变量
    let totalRemain: number = 0;// 总累计变量
    let res: number = 0;// 结果变量就是起点
    for (let i = 0; i < gas.length; i++) {
        currRemain += (gas[i] - cost[i]);
        totalRemain += (gas[i] - cost[i]);
        // 重要，在每一个轮次中都做如下判断
        if (currRemain < 0) {
            currRemain = 0;
            res = i + 1;
        }
    }
    return totalRemain < 0 ? -1 : res;// 结尾处判断总累计变量是否小于0
};


// 这道题目是一道贪心算法的入门题，思想其实非常的巧妙
// 首先在纸上画例子可以思考出第一个结论（很重要）
// 1.那就是如果环绕一圈gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
// 我们可以把这个结论推广到更多的情况，假设你在扫描区间[0,N]，如果当前索引 i 的累加值小于 0
// 那么说明[0, i]间的都不可能作为加油站的起点，利用这个性质我们可以解决这个问题
// 我们设计两个变量，一个总累计变量，一个当前累计变量，扫描这个数组
// 在扫描过程中同时对这两个累计变量做加和操作
// 如果当前累计变量小于0，说明当前索引[0,i]之间的都不可能是起点，我们把起点推测到i + 1，并把当前累加和置为 0，
// 之后我们重复上述判断（在每一个轮次中）,直到扫描完整个数组，然后判断总累计变量时候小于 0
// 如果小于0说明不存在这样的起点，反之当前指向的起点肯定可以满足绕环一周的操作。